The present invention relates to data storage systems, and more particularly, this invention relates to workload-adaptive algorithms for packing compressed logical pages into error correction code (ECC) codewords.
Using Flash memory as an example, the performance characteristics of conventional NAND Flash-based solid state drives (SSDs) are fundamentally different from those of traditional hard disk drives (HDDs). Data in conventional SSDs is typically organized in pages of 4, 8, or 16 KB sizes. Moreover, page read operations in SSDs are typically one order of magnitude faster than write operations and latency neither depends on the current nor the previous location of operations.
However, in Flash-based SSDs, memory locations are erased in blocks prior to being written to. The size of an erase block unit is typically 256 pages and the erase operations takes approximately one order of magnitude more time than a page program operation. Due to the intrinsic properties of NAND Flash, Flash-based SSDs write data out-of-place whereby a mapping table maps logical addresses of the written data to physical ones. This mapping table is typically referred to as the Logical-to-Physical Table (LPT).
As Flash-based memory cells exhibit read errors and/or failures due to wear or other reasons, additional redundancy may be used within memory pages as well as across memory chips (e.g., RAID-5 and RAID-6 like schemes). The additional redundancy within memory pages may include ECC codewords which, for example, may include Bose, Chaudhuri, and Hocquenghem (BCH) codes. Logical pages of memory may be packed into payloads of ECC, whereby the ECC codewords may be used to recover data of the corresponding logical pages.
However, the implementation of ECC codewords with respect to the logical pages of memory has been undesirable in conventional products. Specifically, ECC codewords have a fixed payload size, which limits the amount of data the ECC codeword can protect. Moreover, the fixed payload size of the ECC codewords is not well aligned with the size of uncompressed logical pages in memory. Furthermore, some non-volatile memory systems implement compression of the logical pages in memory, whereby a compressor will compress each logical page to a different size (e.g., length) than its original size. However, the length of a compressed logical page varies depending on the particular logical page and therefore the lengths of various compressed logical pages are inconsistent. This variety in compressed lengths exacerbates the misalignment experienced between the fixed payload size of ECC codewords and the logical pages when compressed logical pages are packed into payloads of ECC codewords.
Conventional attempts to fill the entire payload of ECC codewords result in compressed logical pages undesirably straddling between ECC codewords, thereby resulting in read amplification by requiring that two full ECC codewords be read and transferred from non-volatile memory to a controller in order to read back the single, straddled logical page. Straddling also increase latency when the straddling occurs across a physical page boundary, thereby requiring that two physical pages be read in addition to transferring two full ECC codewords from memory to a controller.
It follows that, a method which overcomes the aforementioned conventional shortcomings by providing an efficient method of filling ECC codeword payloads is greatly desired.